import java.util.Arrays;

class Hash{
    class Node
    {
        int val;
        Node next;
        int key;

        public Node(int key,int val) {
            this.val = val;
            this.key=key;
        }



    }

    Node[]arr=new Node[8];
    public int usesize;
    public void creat(int key,int val)
    {
        //Node b=new Node(key,val);
        int c=key%arr.length;
        Node cur=arr[c];
        while(cur!=null)
        {
            if(cur.key==key)
            {
                cur.val=val;
                return;

            }

            cur=cur.next;
        }

        Node b=new Node(key,val);

        b.next=arr[c];
        arr[c]=b;
        this.usesize++;
        if(load()>0.75)
        {
            kuorong();
        }



    }
    public  double load()
    {

        return (this.usesize)*1.0/this.arr.length;
    }
    public int search(int key)
    {
        int d=key%arr.length;
        Node m=arr[d];
        while(m!=null)
        {
            if(m.key==key)
            {
                return m.val;
            }
            m=m.next;

        }
        return -1;
    }
    public void kuorong()
    {
        Node[]t=new Node[2*arr.length];
        int i=0;
        for(i=0;i<arr.length;i++)
        {
            Node cur=arr[i];
            while(cur!=null)
            {
                Node a=cur;
                int now=cur.key%2*arr.length;
                cur.next=t[now];
                t[now]=cur;
                cur=a;
                cur=cur.next;


            }
        }
        arr=t;
    }

}




public class text69 {
    public static void main(String[] args) {
        Hash b=new Hash();
                b.creat(1,2);
                b.creat(11,4);
                b.creat(2,1);

        //System.out.println(1);
        int c=b.search(11);
        System.out.println(c);


    }
}
